Technical Field
The present invention relates to a technique for reducing the cost of stack scanning in garbage collection (GC) in a computer. More particularly, the present invention relates to a technique for reducing the stack scanning cost in the GC by reusing the previous GC results.
Description of the Related Art
In a recent Java® processing system, generational GC is used to reduce the pause time by the GC, because the GC cost considerably affects the performance of Java® applications. In generational GC, the heap area is split into two areas: a first-generation (nursery) heap area where new objects are allocated, and a second-generation (tenured) heap area where objects that have survived a plurality of times of GC in the first-generation heap area are moved. Usually, only the GC of the first-generation heap area is performed. The GC of the entire heap area is performed only when it has become difficult to prepare sufficient free space. This process reduces the overall GC time.
The GC of the first-generation heap area described above can be performed quickly, as it only checks whether each of the objects present in the area is alive or not. In order to check for the live objects without fail, however, scanning the area, called the “GC root”, is mandatory. The GC roots include static variables, various tables, a “remember set” indicating references from the second-generation heap area, and stack frames of threads.
In a recent large-scale application, the number of stack frames tends to become large, and a large number of threads tend to be generated. The reason this occurs is that recent large-scale applications are often established on various frameworks (e.g., WAS, ICA, IOC, etc.) on Java®, and it has become common to implement other language processing systems (e.g., JRuby, Jython, P8, etc.) on the Java® virtual machine (VM). Accordingly, in a large-scale application, the stack scanning takes a longer time, and the stack scanning cost has become a major factor of overhead for the GC of the first-generation heap area.
Conventional techniques aimed at reducing the GC cost include Patent Literature 1 to 3. Patent Literature 1 discloses the following technique: an object, created by an application program, is created in a thread local heap correlated with one thread, and, in response to a change of the thread which can refer to the created object, the object is moved to an appropriate thread group heap. At the time of collection of an object that has become unnecessary, only the thread that can refer to the unnecessary object is stopped.
Patent Literature 2 discloses the following technique: at the start of an application program, a run-time library is called to analyze the application program to determine whether objects generated are used only inside a method or not. Any object used only inside the method is generated on a frame of a stack area, and the other objects are generated on a heap area.
Patent Literature 3 discloses a memory management device which includes: a garbage collection execution unit; a garbage collection recording unit which records, each time the garbage collection is executed, the number of times of garbage collection and the memory volume after the execution of the garbage collection; an extended memory volume conversion unit which determines, on the basis of the records by the garbage collection recording unit, a memory chart for determining the volume of an extended memory when memory extension is required by the execution of the garbage collection; an extended memory volume storing unit which stores the extended memory volume determined by the extended memory volume conversion unit; and a memory extending unit which refers to the extended memory volume storing unit when memory extension is required for the execution of a program and determines the extended memory volume on the basis of the memory extension chart.
While Patent Literatures 1 to 3 disclose the techniques for reducing the number of times of GC or the execution pause time by the GC, none of these techniques can be applied to the reduction of the time taken by the stack scanning in GC.
Non-Patent Literature 1 discloses the following technique: for a program with a deep stack, the stack scanning cost becomes high. Therefore, for the unchanged stack area, scanning is not repeated, but the results of the previous GC are reused (see Section 5. Generational Stack Collection).
The technique of Non-Patent Literature 1, however, is aimed at early and simple generational GC in which live objects in the first-generation heap area are moved to the second-generation heap area without exception in next GC. This technique does not take into consideration the situation where the stack area, once scanned, still includes a reference to an object residing in the first-generation heap area (hereinafter, such an object will also be called a “nursery object”). Therefore, it is not possible to apply the technique of Non-Patent Literature 1, as it is, to modern generational GC in which an object that has survived a plurality of times of GC in the first-generation heap area is moved to the second-generation heap area.    (Patent Literature 1) Japanese Patent Application Publication No. 2004-246753.    (Patent Literature 2) Japanese Patent Application Publication No. 2004-78750.    (Patent Literature 3) Japanese Patent Application Publication No. 11-312117.    (Non-Patent Literature 1) Perry Cheng, Robert Harper, Peter Lee, “Generational Stack Collection and Profile-Driven Pretenuring”, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, pp. 162-173, Jun. 17-19, 1998, Montreal, Quebec, Canada.